package com.lfg.leetcode.leetcode500;


import java.util.*;

public class No740deleteAndEarn {
    public static void main(String[] args) {
        System.out.println(deleteAndEarn(new int[]{1, 1, 2, 1, 1}));
        System.out.println(deleteAndEarn(new int[]{1, 2, 2, 3, 4}));
        System.out.println(deleteAndEarn(new int[]{2, 1, 3, 3, 2, 2}));
        System.out.println(deleteAndEarn(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 10, 4, 4, 3, 3, 2, 2, 1, 1}));
    }

    public static int deleteAndEarn(int[] nums) {
        int ret = 0;
        Arrays.sort(nums);
        int lastNum = nums[0];
        List<Integer> value = new ArrayList<>();
        value.add(lastNum);

        for (int i = 1;i<nums.length;i++) {
            if(nums[i] == nums[i-1]){
                value.set(value.size()-1, value.get(value.size()-1)+nums[i]);
            }else if(nums[i] == nums[i-1] + 1){
                value.add(nums[i]);
            }else{
                ret += rob(value);
                value.clear();
                value.add(nums[i]);
            }
        }
        ret += rob(value);
        return ret;
    }
    public static  int rob(List<Integer> list){
        if(list.size() == 1){
            return list.get(0);
        }
        int[] dp = new int[list.size()];
        dp[0] = list.get(0);

        dp[1] = Math.max(dp[0], list.get(1));
        for(int i=2;i<list.size();i++){
            dp[i] = Math.max(dp[i-2]+ list.get(i), dp[i-1]);
        }
        return dp[dp.length-1];
    }

}



